package chart.树的遍历;

import chart.TreeNode;

import java.io.Serializable;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/13 15:31
 * 前序遍历 - 根 -> 左子树 -> 右子树
 */
public class PreOrder implements Serializable {
    private static final long serialVersionUID = 6244055131567143855L;

    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode(4, new TreeNode(2, new TreeNode(1, new TreeNode(0), null), new TreeNode(3, null, null)),
                new TreeNode(6, null, null));
        preOrderRecurse(root);
        System.out.println();
        preOrderIterate(root);
    }

    /**
     * 递归
     *
     * @param node 参数
     */
    static void preOrderRecurse(TreeNode<Integer> node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        if (node.left != null) preOrderRecurse(node.left);
        if (node.right != null) preOrderRecurse(node.right);
    }

    /**
     * 迭代
     *
     * @param root 参数
     */
    static void preOrderIterate(TreeNode<Integer> root) {
        if (root == null) return;
        Deque<TreeNode<Integer>> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            final TreeNode<Integer> pop = stack.pop();
            System.out.print(pop.val + " ");
            if (pop.right != null) stack.push(pop.right);
            if (pop.left != null) stack.push(pop.left);
        }
    }

    static void preOrderIteratorV2(TreeNode<Integer> node) {
        Stack<TreeNode<Integer>> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                System.out.print(node.val + " ");
                stack.push(node);
                node = node.left;
            }
            // stack.pop 永远有值, 因为 !stack.isEmpty() 才会执行这步
            else node = stack.pop().right;
        }
        System.out.println();
    }

}










